
import random

dim = 3

mz = []
path = []

times = 0
maxdeepth = 0
ss = 0

def gen_mz():
    
    for i in range(dim+1):
        # path.append((i,i))
        mz.append([])
        for j in range(dim+1):
            v = 0 if random.randint(0, 100)< 90 else 1
            # print(v, end="")
            mz[i].append(v)
            
    mz[0][0] = 0 
    mz[dim][dim] = 0
    
    return mz

def show_mz() -> None:
    print("-"*(dim+1))
    print("\n".join([
        "".join(["#" if c == 1 else " " if (x,y) not in path else "." for x,c in enumerate(row)]) + "|"
        for y,row in enumerate(mz)
    ]))


def step(x,y):
    steps = [
        (x+1,y), (x,y+1), (x-1,y), (x,y-1)
    ]
    # print("step:", steps)
    steps = [s for s in steps if s[0]>=0 and s[0]<=dim and s[1]>=0 and s[1]<=dim]
    return steps

def road(x,y,pre,deepth = 0):

    global times
    global maxdeepth
    
    times += 1
    maxdeepth = max(deepth, maxdeepth)
    
    # print(x,y,deepth, end="\r")
    
    nx = step(x,y)
    # nx = [s for s in nx if s not in pre]
    # print(nx)

    for n in nx:
        # print("nx:",n)

        if n in pre:
            continue
        
        i,j = n
        if i == dim and j == dim:
            pre.append(n)
            # print("end:",deepth,pre)
            
            global path
            path = pre
            # show_mz()

            global ss
            ss += 1
            
            return True
        
        if mz[j][i] > 0:
            continue
        
        # print(":",(x,y),n)

        # !!! 此处需要 copy
        pre2 = pre.copy()
        pre2.append(n)
        road(i,j,pre2, deepth+1)
        
    pass

if __name__ == "__main__":
    # print(step(1,1))
    
    mz = gen_mz()
    show_mz()
    
    road(0,0,[])
    show_mz()
    
    print("success times:",ss)
    print("times:",times)
    print("maxdeepth:",maxdeepth)
    